#include <iostream>
#include <vector>
//实现堆排序
/*
实现需要的数据结构 大根堆：
	在stl中是priority_queue<int, vector<int>, less<int>>
	堆就是在数组上实现的完全二叉树，如下就是[5 4 3 2 1]
	 5
	/\
   4  3
   /\
  2  1
  其中数组下标i的子左右节点为2k+1 2k+2

*/


//交换函数，需要要求在k节点下的子节点满足是一个大根堆
//arrLen实际是arr的边界
void swapF(int k, std::vector<int> &arr, int arrLen)
{

	//int arrLen = arr.size();
	int left = 2*k+1;
	int right = 2*k+2;
	int father = k;
	if (left < arrLen && arr[left] > arr[father])
	{
		father = left;
	}
	if (right < arrLen && arr[right] > arr[father])
	{
		father = right;
	}
	if (father != k)
	{
		int t = arr[father];
		arr[father] = arr[k];
		arr[k] = t;
		/*
			递归保证k以后的节点为大根堆,如下
			若将2，5互换，则2，4，1仍然不是大根堆
				 2
				/\
			   5  3
			  /\
             4  1
		*/
		swapF(father, arr, arrLen);
	}
}

void buildMaxHeap(std::vector<int>& arr)
{
	for (int i = arr.size() / 2; i>=0; --i)
	{
		swapF(i, arr, arr.size());
	}
}

void heapSort(std::vector<int>& arr)
{
	buildMaxHeap(arr);
	for (int i = arr.size() - 1; i > 0; --i)
	{
		//将最大值提到数组最前面，实现从小到大排序
		int t = arr[0];
		arr[0] = arr[i];
		arr[i] = t;

		// 重构大根堆，因为根节点以下全满足大根堆，
		// 所以可以用swapF调整,注意边界不能包括已排序的部分
		swapF(0, arr, i);
	}
	
}

int main()
{
	std::vector<int> arr{3,4,5,3,1,7,8,7,0,13,22,4,1,2,6,7382,33,2231,312312,4341,3131,1231241,1231232,122,3213,132312,3124,5754,7765,32423,4654,234234,23342,345,757,87,980};
	heapSort(arr);
	for (auto i : arr)
	{
		std::cout << i << std::endl;
	}

	return 0;
}